package com.cyh.pangu.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cuiyh9
 * @date 2020/8/27
 */
public class Offer10_2 {
    Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 3) {
            return n;
        }
        if (numMap.get(n) != null) {
            return numMap.get(n);
        }
        int num = (numWays(n-2) + numWays(n-1)) % 1000000007;
        numMap.put(n, num);
        return num;
    }
}
